/*
https://leetcode-cn.com/problems/tallest-billboard/solution/zui-gao-de-yan-gao-pai-by-leetcode/
 */
import java.util.Arrays;

public class Solution956 {

    int[][] f;

    public int tallestBillboard(int[] rods) {
        f=new int[rods.length][10001];
        for (int i=0;i<f.length;i++){
            Arrays.fill(f[i],-1);
        }
        return dfs(rods,0,5000);
    }

    private int dfs(int[] rods, int k, int t) {
        if (k==rods.length){
            if (t==5000){
                return 0;
            }else {
                return Integer.MIN_VALUE/3;
            }
        }else if (f[k][t]!=-1){
            return f[k][t];
        }else{
            int ans=dfs(rods,k+1,t);
            ans=Math.max(ans,dfs(rods,k+1,t-rods[k]));
            ans=Math.max(ans,dfs(rods,k+1,t+rods[k])+rods[k]);
            f[k][t]=ans;
            return ans;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution956().tallestBillboard(new int[]{1,2,3,4,5,6}));
    }
}
